Since the advent of digital computing techniques thirty five years ago, attention has focused on methods for reducing errors in data. Such errors may be attributable to transient conditions in a computing apparatus or transmission channel, called "soft" errors; or they may be recurrent errors, such as those resulting from defects in data storage media, etc., called "hard" errors. In either event, in order to insure the integrity of data it has early recognized that errors must be located and corrected. For example, an error rate of 10.sup.-12 bits (i.e. one error bit in 10.sup.12 bits) is a typical performance specification for hard errors in a high capacity disk data storage subsystem.
Many different types of block and convolutional error detection and/or correction codes have been devised and have been applied to reduce error rates typically associated with different types of data paths and storage media. These codes are frequently named after the people who first devised or disclosed the particular code. For instance, such codes as Hamming codes, Fire codes, Golay code, Bose-Chaudhuri-Hocquenghem (BCH) codes, Reed-Solomon (RS) codes, and Goppa codes are known and used in the prior art and were introduced by the persons whose surnames have come to identify the particular code. The characteristics of these codes are summarized and explained in general terms in a recent article by Solomon W. Golomb entitled "Optical Disk Error Correction" appearing in Byte Magazine, Vol. 11, No. 5, May 1986, pages 203 to 210.
Rotating disk data storage devices typically store data as discrete blocks or frames, with each frame being related to a single data track or sector within a track. Commonly employed frame lengths are 256 (2.sup.8), 512 (2.sup.9) and 1024 (2.sup.10) bytes. As a result of this characteristic of disk stores, one currently popular code for use in error correction processes associated therewith is the Reed-Solomon (RS) code method. This code treats m-bit bytes as individual code symbols. A single RS code word, or "frame" of data (including overhead associated with the error correction process) can be up to 2.sup.m -1 of m-bit bytes. If it is desired to correct any error that affects up to and no more than t bytes per frame, then the RS methodology requires that 2t bytes per frame be devoted to error correction redundancy or overhead. This leaves 2.sup.m -1-2t bytes available for useful data storage and retrieval.
While RS codes are becoming popular for error correction in disk stores, implementation of RS code methods has heretofore been very complicated and has required a considerable overhead of hardware devoted to carrying out the error correction process. One example of the complexity of hardware required for real time error correction with RS codes is U.S. Pat. No. 4,494,234 to Patel. In the prior approach described in the Patel patent, literally thousands of discrete logic circuit elements were required in order for the dedicated hardware apparatus to carry out error correction on the fly. A related Patel patent directed to the syndrome processing unit of the on the fly system patented by the referenced U.S. Pat. No. 4,494,234, is U.S. Pat. No. 4,504,948 which provides further useful background information relating to the processing required to correct errors based on Reed Solomon correction codes employing finite field theory. It, too, is extremely complicated and expensive, although effective for multi-byte error correction within the finite field data block.
One hitherto unsolved need has arisen for an effective RS error correction code system in which the special hardware requirements imposed by the process have been minimized.
One recognized phenomenon in rotating disk data storage devices is the tendency of data errors to cluster. An electrical transient condition, for example, may cause two or three adjacent bytes to become corrupted with errors. One known approach for minimizing the impact of cluster errors in error correction processing is to divide a data block into several subfields and to develop error syndromes based upon the interleave of the subfields. In this way, if error clusters occur, they will likely be spread over the several subfields. If each subfield of a particular block or sector is denominated an RS frame, the number of bytes t to be corrected for the frame may be made low, and the consequent error correction overhead (2t) per frame may also be kept low, while overall corrected error rates are extremely low. A need has arisen for RS error correction code apparatus which makes use of an interleave approach in order thereby to simplify and minimize the hardware required.
Since error correction is an occasional, as opposed to a constant, process, and the calculations required to perform RS error correction involve complex mathematics, a need has arisen to employ minimized logic to generate an error correction value or "syndrome" for each RS frame during data write operations, and to recover and check its "syndrome" during data read operations; and, to employ a general purpose digital microprocessor with a program subroutine for carrying out the intermittant and complex RS calculations necessitated when a detected non-zero syndrome reveals the presence of one or more errors in the RS frame.